|
|
Algebraický přístup k CSP
Bulín, Jakub ; Barto, Libor (vedoucí práce) ; Růžička, Pavel (oponent)
Nechť A je konečná relační struktura. Problém splňování omezení s šablonou A, CSP (a), rozhoduje, zda vstupní struktura X je homomorfní A. Hypotéza o dichotomii CSP Federa a Vardiho říká, že CSP(A) je vždy buď v P nebo NP-úplný. V první části předsdtavíme algebraický přístup k CSP a shrneme známé výsledky o CSP pro orientované grafy, tzv. H-barvení. Ve druhé části se zabýváme jistou třídou orientovaných stromů, tzv. speciálními polyádami. Pomocí algebraického přístupu potvrdíme dichotomickou hypotézu pro speciální polyády. V polynomiálním případě poskytneme jemnější popis a zkontruujeme speciální polyádu T takovou, že CSP(T) je v P, ale T nemá šířku 1 ani žádné near-unanimity polymorfismy.
|
|
|
Constraint satisfaction, graphs and algebras
Bulín, Jakub ; Barto, Libor (vedoucí práce) ; Růžička, Pavel (oponent) ; Bulatov, Andrei (oponent)
CSP, grafy a algebry Jakub Bulín Abstrakt Tato práce sestává ze tří článků v oblasti algebraického přístupu k problému splňování podmínek (CSP). V prvním článku, se spoluautory Deli'cem, Jacksonem a Nivenem, studujeme redukci CSP na orientované grafy. Pro každou relační strukturu A konstruujeme orientovaný graf D(A) takový, že CSP(A) a CSP(D(A)) jsou logspace ekvivalentní a většina rele- vantních vlastností se přenáší z A na D(A). Důsledkem je, že algebraické hypotézy charekterizující CSP řešitelné v P, NL a L jsou ekvivalentní je- jich restrikcím na orientované grafy. Ve druhém článku dokazujeme, že pro danou core relační strukturu A s konečnou šířkou a B ⊆ A lze algorit- micky rozhodnout, zda je B absorbující podalgebra algebry polymorfismů A. Jako vedlejší produkt získáváme, že Jónssonova absorpce se v tomto případě shoduje s obvyklou absorpcí. Ve třetím článku, za použití mod- erních algebraických nástrojů (např. teorie absorpce a pointující operace), potvrzujeme hypotézu o dichotomii CSP pro tzv. speciální orientované stromy. Konkrétně, core speciální stromy řešitelné v P mají konečnou šířku. Klíčová slova: problém splňování omezení, algebra polymorfismů, ab- sorbující podalgebra, konečná...
|
|
|
Algebraický přístup k CSP
Bulín, Jakub ; Barto, Libor (vedoucí práce) ; Růžička, Pavel (oponent)
Nechť A je konečná relační struktura. Problém splňování omezení s šablonou A, CSP (a), rozhoduje, zda vstupní struktura X je homomorfní A. Hypotéza o dichotomii CSP Federa a Vardiho říká, že CSP(A) je vždy buď v P nebo NP-úplný. V první části předsdtavíme algebraický přístup k CSP a shrneme známé výsledky o CSP pro orientované grafy, tzv. H-barvení. Ve druhé části se zabýváme jistou třídou orientovaných stromů, tzv. speciálními polyádami. Pomocí algebraického přístupu potvrdíme dichotomickou hypotézu pro speciální polyády. V polynomiálním případě poskytneme jemnější popis a zkontruujeme speciální polyádu T takovou, že CSP(T) je v P, ale T nemá šířku 1 ani žádné near-unanimity polymorfismy.
|
host ::
RSS.